% IEEE Paper Template for US-LETTER Page Size (V1)
% Sample Conference Paper using IEEE LaTeX style file for US-LETTER pagesize.
% Copyright (C) 2006-2008 Causal Productions Pty Ltd.
% Permission is granted to distribute and revise this file provided that
% this header remains intact.
%
% REVISION HISTORY
% 20080211 changed some space characters in the title-author block
%
\documentclass[10pt,conference,letterpaper]{IEEEtran}
\usepackage{times,amsmath,epsfig}
\usepackage{graphicx}
%
\title{Technical Report on Ellipse Drawing Algorithm}
%
\author{%
% author names are typeset in 11pt, which is the default size in the author block
{Baurisetty Dhiraj}%
% add some space between author names and affils
\vspace{1.6mm}\\
%\fontsize{10}{10}\selectfont\itshape
% 20080211 CAUSAL PRODUCTIONS
% separate superscript on following line from affiliation using narrow space
\,MT2012032 \\ Computer Graphics\,\\ 
International Institute Of Information Technology\\
%\fontsize{9}{9}\selectfont\ttfamily\upshape
%
% 20080211 CAUSAL PRODUCTIONS
% in the following email addresses, separate the superscript from the email address 
% using a narrow space \,
% the reason is that Acrobat Reader has an option to auto-detect urls and email
% addresses, and make them 'hot'.  Without a narrow space, the superscript is included
% in the email address and corrupts it.
% Also, removed ~ from pre-superscript since it does not seem to serve any purpose
\,dhiraj.baurisetty@iiitb.org%
% add some space between email and affil
\vspace{1.2mm}\\
\fontsize{10}{10}\selectfont\rmfamily\itshape
% 20080211 CAUSAL PRODUCTIONS
% separated superscript on following line from affiliation using narrow space \,

\fontsize{9}{9}\selectfont\ttfamily\upshape
% 20080211 CAUSAL PRODUCTIONS
% removed ~ from pre-superscript since it does not seem to serve any purpose
}
%
\def \i {$_{i}$}
\def \2 {$^{2}$}
\begin{document}
\maketitle
%
\begin{abstract} 
The technical report will contain the background of the mid-point algorithm proposed by Jerry R. Van Aken used to draw an ellipse on raster displays. The report will also discuss the impact of this algorithm on the Computer Graphics community and the areas where it is being used extensively.
\end{abstract}

% NOTE keywords are not used for conference papers so do not populate them
% \begin{keywords}
% keyword-1, keyword-2, keyword-3
% \end{keywords}
%

\section{Introduction}
The mid-point algorithm that is going to be discussed in the subsequent sections was proposed by Jerry R. Van Aken. This algorithm comes embedded nowadays in the computer graphics library in order to draw an ellipse on raster displays. The algorithm is famous mostly because of its accuracy and the bounded error advantage of the algorithm that will also be discussed later.

On some of the display devices, the pixel cells may be rectangular. In those devices, a circular figure can only be achieved by drawing an ellipse. The mid-point algorithm generates pixels that have to be drawn on the display.

The two point algorithm by Bresenham will also be discussed in the report and it will be compared against the mid-point algorithm for similarities and dissimilarities.

\section{Mid-Point Algorithm}

\subsection{Construction}

\begin{figure}[ht!]
\centering
\includegraphics[width=90mm]{/home/dhiraj/Desktop/image.png}
\caption{Ellipse partitioned into two regions}
\label{overflow}
\end{figure} \\

Consider the first quadrant where x$\geq$0 and y$\geq$0. Let a be the semi-major axis and b be the semi-minor axis.\\
Let us take three pixels B,C and D such that B=(x\i - 1,y\i), C=(x\i - 1,y\i + 1) and D=(x\i,y\i + 1)
Now the following steps are followed:

\begin{itemize}
\item	A pixel is found at which the slope of the tangent will be -1 i.e at (x\i,y\i) such that $\frac{dy}{dx}$=-1 given the semi-major and semi-minor axis. \\
Now this pixel will divide the region into two halves: One on the right and one on the left. Let the region on the right be region 2 and the region on the left be region 1.\\
For every pixel (x,y) already selected in region 2, the next pixel will be selected from either C or D\\

Similarly for every pixel (x\i,y\i) already selected in region 1, the next pixel will be selected from either B or C.\\

\item	Let us consider region 2 first. As we know the equation of an ellipse is  f(x,y)=b\2 x\2 + a\2 y\2 - a\2 b\2 . Now we find the mid point of CD which is (x\i\ - $\frac{1}{2}$,y\i\ + 1) and name it M.

\item Now we calculate two decision variables namely d1\i and d2\i .\\ d1\i is calculated as 2f(x\i\ - $\frac{1}{2}$ , y\i\ + 1) (Midpoint of Line segment joining CD) which gives b\2 (2x\i \2\ - 2x\i + $\frac{1}{2}$)+ a\2 (2y\i \2 + 4y\i + 2) - 2a\2 b\2 .\\ If d1\i \textless\ 0, then D is selected and if d1\i \textgreater\ 0, then C is selected. \\ At the same time, another decision variable d2\i\ is calculated as 2f(x\i\ - 1 , y\i + $\frac{1}{2}$ ) (Midpoint of Line segment joining CD) which gives b\2 (2x\i \2 - 4x\i + 2)+a\2 (2y\i \2 + 2y\i + $\frac{1}{2}$) - 2a\2 b\2 . 

\begin{figure}[ht!]
\centering
\includegraphics[width=90mm]{/home/dhiraj/Desktop/image1.png}
\caption{Selection of pixel in region 2}
\label{overflow}
\end{figure} \\

\begin{figure}[ht!]
\centering
\includegraphics[width=90mm]{/home/dhiraj/Desktop/image2.png}
\caption{Selection of pixel in region 1}
\label{overflow}
\end{figure} \\

\item At every step, d2\i\ is calculated along with d1\i\ . The moment d2\i\ is found to be zero, it indicates that region 2 has ended and region 1 has started. Now the value of d1 is no longer needed.\\
If d2\i\ \textless\ 0, then C is selected and if d2\i\ \textgreater\ 0, then B is selected as the next pixel in region 1 to be coloured.

\end{itemize}

\subsection{Error in Mid Point Algorithm}
The maximum error that is possible in mid-point algorithm is $\frac{1}{2}$. This is because say the value of f(x,y) at the midpoint of CD was 0. So the curve will pass through both C and D. Taking unity as the distance between C and D, the maximum error can be $\frac{1}{2}$ as C and D will be at a distance of $\frac{1}{2}$ from the midpoint.\\
In another case, if the curve passes at a distance x from the mid point of CD, then the pixel that will be selected will always be at a distance less than $\frac{1}{2}$ from the point of intersection of the line say CD and the point at which the curve meets the line.

\subsection{Advantages}
\begin{itemize}
\item	The mid-point algorithm requires only few integer additions per pixel.
\item   This algorithm provides an excellent control over linear error that is the maximum error lies between $\frac{-1}{2}$ and $\frac{1}{2}$
\item   The algorithm also has only addition operations in the program loops making it simple and fast to implement in all processors.
\end{itemize}

The reason why this algorithm was proposed because the simple extension of Bresenham's line drawing algorithm was not sufficient to draw an accurate ellipse.

\section{Two Point Algorithm}

The Bresenham's two point algorithm can also be extended to draw an ellipse on raster displays.

\subsection{Construction}

Consider the first quadrant where x$\geq$0 and y$\geq$0. Let a be the semi-major axis and b be the semi-minor axis.\\
Let us take three pixels B,C and D such that B=(x\i - 1,y\i), C=(x\i - 1,y\i + 1) and D=(x\i,y\i + 1)
Now the following steps are followed:

\begin{itemize}
\item	A pixel is found at which the slope of the tangent will be -1 i.e at (x\i,y\i) such that $\frac{dy}{dx}$=-1 given the semi-major and semi-minor axis. \\
Now this pixel will divide the region into two halves: One on the right and one on the left. Let the region on the right be region 2 and the region on the left be region 1.\\
For every pixel (x,y) already selected in region 2, the next pixel will be selected from either C or D\\

Similarly for every pixel (x\i,y\i) already selected in region 1, the next pixel will be selected from either B or C.\\

\item	Let us consider region 2 first. The equation of an ellipse is  f(x,y)=b\2 x\2 + a\2 y\2 - a\2 b\2 .

\item Now we calculate two decision variables namely d1\i and d2\i .\\ Also let e1 be the value of f(x,y) at D , e2 be the value of f(x,y) at C and e3 be the value of f(x,y) at B. d1\i\ is calculated as $|$e1$|$-$|$e2$|$.\\
At the same time d2\i\ is also calculated as $|$e2$|$-$|$e3$|$.\\
If d1\i\ \textless\ 0 then, D is selected to be coloured. Else if d1\i\ \textgreater\ 0, then C is selected. \\

\item At every step, d2 is calculated along with d1. The moment d2 is found to be zero, it indicates that region 2 has ended and region 1 has started. Now the value of d1 is no longer needed.

\item Now if d2 \textless\ 0, then C is selected and if d2 \textgreater\ 0, then B is selected as the next pixel in region 1 to be coloured.

\end{itemize}

\subsection{Error in Two Point Algorithm}
The biggest disadvantage of Two Point Algorithm is that the error increases as the ratio of a/b increases where 'a' is the semi-major axis and 'b' is the semi-minor axis. Unlike in mid-point algorithm where the error is bounded within $\frac{-1}{2}$ and $\frac{1}{2}$ .

\subsection{Difference between Two Point Algorithm and Mid-Point Algorithm}
The important difference between the Two Point Algorithm and Mid-Point Algorithm is that in the Two Point Algorithm, the error is not bounded whereas in the Mid-Point Algorithm, the error is bounded between $\frac{-1}{2}$ and $\frac{1}{2}$ .

\section{Impact on Graphics Community}
The mid-point algorithm helps in accurately displaying the ellipse on raster displays. Because of the bounded error property of the algorithm, it is preferred in displaying ellipse over the Two-Point algorithm. The algorithm comes embedded in graphics libraries.Since only integer point calculations are done, it becomes easy to compute the coordinates of the ellipse.

\begin{thebibliography}{1}
\bibitem{son03}
Van Aken, J.R.,1984, \newblock ``An Efficient Ellipse-Drawing Algorithm," \newblock
Computer Graphics and Applications, IEEE, 4(9), 24-35.

\end{thebibliography}
\end{document}
